#include <stdio.h>
#include <math.h>
#include <time.h>

// Largest prime factor
// Problem 3
// The prime factors of 13195 are 5, 7, 13 and 29.
// What is the largest prime factor of the number 600851475143 ?

int IsPrime(long n);

void main(void)
{
    clock_t begin, end;
	double time_spent;
	long long number = 600851475143;
	int i;

	begin = clock();
	        
    for(i = 2; i < number; i++)
    {
	    if(number % i == 0 && IsPrime(i))
	    {
		    number = number / i;		
	    }
    }

    printf("%d", number);
	
	end = clock();
	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    
	printf("Time: %d", time_spent); 
}

int IsPrime(long n)
{
	int i;
	long m;

    if (n < 2)
    {
        return 0;
    };

    if (n % 2 == 0)
    {
        return (n == 2);
    }

    m = sqrt((double)n);

    for (i = 3; i <= m; i += 2)
    {
        if (n % i == 0)
        {
            return 0;
        }
    }

    return 1;
}